package leetcode.code0862;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int shortestSubarray(int[] nums, int k) {
		int N = nums.length;
		long[] sum = new long[N + 1];
		for (int i = 0; i < N; i++) {
			sum[i + 1] = sum[i] + nums[i];
		}
		int ans = Integer.MAX_VALUE;
		int[] dq = new int[N + 1];
		for (int i = 0, l = 0, r = 0; i < N + 1; i++) {
			// 头部开始，符合条件的，从头部弹出！
			while (l != r && sum[i] - sum[dq[l]] >= k) {
				ans = Math.min(ans, i - dq[l++]);
			}
			// 尾部开始，前缀和比当前的前缀和大于等于的，从尾部弹出！
			while (l != r && sum[dq[r - 1]] >= sum[i]) {
				r--;
			}
			dq[r++] = i;
		}
		return ans != Integer.MAX_VALUE ? ans : -1;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(2, this.shortestSubarray(HelpDebug.str2array3("[-300,3,-4,3,2,-300]"), 4));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
